package com.atwulidun.kruskal07;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Kruskal {
    public static void main(String[] args) {
        // 保存顶点数据的一维数组
        char[] data = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        //克鲁斯卡尔算法的邻接矩阵
        int[][] weight = {
                    /*A*/ /*B*/ /*C*/ /*D*/ /*E*/ /*F*/ /*G*/
                /*A*/ {0, 12, Graph.INF, Graph.INF, Graph.INF, 16, 14},
                /*B*/ {12, 0, 10, Graph.INF, Graph.INF, 7, Graph.INF},
                /*C*/ {Graph.INF, 10, 0, 3, 5, 6, Graph.INF},
                /*D*/ {Graph.INF, Graph.INF, 3, 0, 4, Graph.INF, Graph.INF},
                /*E*/ {Graph.INF, Graph.INF, 5, 4, 0, 2, 8},
                /*F*/ {16, 7, 6, Graph.INF, 2, 0, 9},
                /*G*/ {14, Graph.INF, Graph.INF, Graph.INF, 8, 9, 0}};
        // 创建一个图对象
        Graph graph = new Graph(data, weight);
        // 调用kruskal方法
        MinTree.kruskal(graph);
    }
}

// 最小生成树类
class MinTree {
    public static void kruskal(Graph graph) {
        // 获取该图对象的边对象列表
        List<Edge> allEdges = graph.getEdges();
        // 对该边对象列表按照权值从小到大的顺序进行排序
        Collections.sort(allEdges);

        // 创建一个List<Edge>来保存当前最小生成树所包含的边对象，符合要求的边对象会不断地被添加进来
        List<Edge> resultEdges = new ArrayList<>();

        // 创建一个一维数组来保存图对象的每个顶点所对应的终点
        int[] ends = new int[graph.getData().length];

        // 遍历边对象列表，寻找合适的边对象并将其加入到resultEdges中
        for (Edge allEdge : allEdges) {
            // 获取当前边对象的第一个顶点的坐标
            int start = graph.getPosition(allEdge.getStart());
            // 获取当前边对象的另一个顶点的坐标
            int end = graph.getPosition(allEdge.getEnd());
            // 若该边对象的两个顶点都有同一个终点，那么会形成闭合回路，不符合条件！！！！！！！！
            // 获取当前边对象两个顶点的终点坐标
            int m = graph.getEnd(ends, start);
            int n = graph.getEnd(ends, end);
            // 若两个顶点的终点不相等，那么该边符合条件
            if (m != n) {
                // 进一步生成最小生成树，即将当前边对象加入到resultEdges中
                resultEdges.add(allEdge);
                // 进一步给ends数组进行赋值
                ends[m] = n;
            }
        }
        // 打印resultEdges
        for (Edge resultEdge : resultEdges) {
            System.out.println(resultEdge);
        }
    }
}

// 图类
class Graph {
    // 记录顶点的一维数组
    private char[] data;

    // 邻接矩阵
    private int[][] weight;
    // 存放边对象的集合
    private List<Edge> edges;
    // 存放边数量的变量
    private int edgeNum;

    // 表示两个顶点间不互相联通的常量
    public static final int INF = Integer.MAX_VALUE;

    // 注意：为了不对传进来的data和weight造成影响，这里使用复制初始化的方式
    // 带权的无向联通图
    public Graph(char[] data, int[][] weight) {
        // 给data和weight初始化
        this.data = new char[data.length];
        this.weight = new int[data.length][data.length];
        for (int i = 0; i < data.length; i++) {
            this.data[i] = data[i];
            System.arraycopy(weight[i], 0, this.weight[i], 0, data.length);
        }
        // 给edges和edgeNum初始化
        // 注意：由于是无向图，故创建对象时第二层循环从i+1开始，既避免了一条边的两个顶点相同，也避免了重复创建对象
        edges = new ArrayList<>();
        for (int i = 0; i < data.length; i++) {
            for (int j = i + 1; j < data.length; j++) {
                // 根据邻接矩阵创建相应的边对象加入到edges中
                if (weight[i][j] != INF) {
                    edges.add(new Edge(weight[i][j], data[i], data[j]));
                }
            }
        }
        edgeNum = edges.size();
    }

    // 打印邻接矩阵的方法
    public void show() {
        for (int[] ints : weight) {
            for (int anInt : ints) {
                System.out.printf("%12d\t", anInt);
            }
            System.out.println();
        }
    }

    // 根据顶点data获取顶点坐标的方法
    public int getPosition(char vertex) {
        for (int i = 0; i < data.length; i++) {
            if (vertex == data[i]) {
                return i;
            }
        }
        return -1;// 若没找到该字符
    }

    // 根据当前”最小生成树“所有顶点对应的 “终点” 数组来获取当前“最小生成树”里某个顶点的终点坐标的方法
    // 注意：ends是在最小生成树不断生成的的过程中不断被赋值的
    public int getEnd(int[] ends, int i) {
        while (ends[i] != 0) {
            i = ends[i];
        }
        // 如果ends[i] == 0，那么i对应的顶点的终点就是本身
        return i;
    }

    public char[] getData() {
        return data;
    }

    public void setData(char[] data) {
        this.data = data;
    }

    public int[][] getWeight() {
        return weight;
    }

    public void setWeight(int[][] weight) {
        this.weight = weight;
    }

    public List<Edge> getEdges() {
        return edges;
    }

    public void setEdges(List<Edge> edges) {
        this.edges = edges;
    }

    public int getEdgeNum() {
        return edgeNum;
    }

    public void setEdgeNum(int edgeNum) {
        this.edgeNum = edgeNum;
    }
}

// 边类(因为需要对边的权值进行从小到大排列，因此实现Comparable接口)
class Edge implements Comparable<Edge> {
    // 边的权值
    private int weight;
    // 边的第一个顶点
    private char start;
    // 边的另一个顶点
    private char end;

    public Edge(int weight, char start, char end) {
        this.weight = weight;
        this.start = start;
        this.end = end;
    }

    public int getWeight() {
        return weight;
    }

    public void setWeight(int weight) {
        this.weight = weight;
    }

    public char getStart() {
        return start;
    }

    public void setStart(char start) {
        this.start = start;
    }

    public char getEnd() {
        return end;
    }

    public void setEnd(char end) {
        this.end = end;
    }

    @Override
    public String toString() {
        return "Edge{" +
                "weight=" + weight +
                ", start=" + start +
                ", end=" + end +
                '}';
    }

    @Override
    public int compareTo(Edge o) {
        return weight - o.weight;
    }
}
